#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;


int findDuplicate(vector<int> &nums) {
    //快慢指针
    int fast = 0;
    int low = 0;

    while (true) {
        fast = nums[nums[fast]];
        low = nums[low];
        //如果快慢指针相同 把快指针定为首 然后共同移动一步当他们相遇的时候就
        //相同了
        if (fast == low) {
            fast = 0;

            while (nums[low] != nums[fast]) {
                fast = nums[fast];
                low = nums[low];
            }
            return nums[low];
        }

    }

    //return -1;
}